package com.example.merge;


public class MergeSolution {

    /**
     * @author zhy
     * @version 1.0.0
     * @ClassName Solution.java
     * @Description 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
     * 输入：
     * nums1 = [1,2,3,0,0,0], m = 3
     * nums2 = [2,5,6],       n = 3
     * <p>
     * 输出：[1,2,2,3,5,6]
     * @createTime 2020年11月16日 15:27:00
     */
    public static int[] mergeArray(int[] A, int m, int[] B, int n) {
        int pa = 0, pb = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (pa < m || pb < n) {
            if (pa == m) {
                cur = B[pb++];
            } else if (pb == n) {
                cur = A[pa++];
            } else if (A[pa] < B[pb] && A[pa] != 0) {
                cur = A[pa++];
            } else {
                cur = B[pb++];
            }
            sorted[pa + pb - 1] = cur;
        }
        cur = 0;
        for (int i = 0; i != m + n; ++i) {
            if (sorted[i] != 0) {
                A[cur++] = sorted[i];
            }
        }
        return A;
    }

    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int max = m + n - 1;
        int i = m - 1;
        int j = n - 1;
        while (i >= 0 && j >= 0) {

        }

    }

    /**
     * 合并两个有序的链表
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode(0), cur = dum;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dum.next;
    }

    class ListNode {

        int val;

        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public void merge3(int[] A, int m, int[] B, int n) {
        int pa = m - 1, pb = n - 1;
        int tail = m + n - 1;
        int cur;
        while (pa >= 0 || pb >= 0) {
            if (pa == -1) {
                cur = B[pb--];
            } else if (pb == -1) {
                cur = A[pa--];
            } else if (A[pa] > B[pb]) {
                cur = A[pa--];
            } else {
                cur = B[pb--];
            }
            A[tail--] = cur;
        }

    }

    public static void main(String[] args) {
//        int[] nums1 = new int[]{1, 2, 3, 0, 0, 0};
//        int[] nums2 = new int[]{2, 5, 6};
//        int[] result = mergeArray(nums1, nums1.length, nums2, nums2.length);
//        for (int i = 0; i < result.length; i++) {
//            System.out.println(result[i]);
//        }
        int[][] a = new int[][]{};
        a[0] = new int[]{0};

    }
}
